#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define RED     0
#define BLACK   1
typedef int     Type;

typedef struct RBTreeNode {
    unsigned char       color;
    Type                key;
    struct RBTreeNode   *left;
    struct RBTreeNode   *right;
    struct RBTreeNode   *parent;
} Node, *RBTree;

void printNodeInfo(Node *node) {
    printf("node: %d \nparent: %d \nuncle: %d \nleft child: %d \nright child: %d \n", node->key, node->parent ? node->parent->key : -1, node->parent && node->parent->left == node ? node->parent->right->key : node->parent->left->key, node->left ? node->left->key : -1, node->right ? node->right->key : -1);
}

RBTree root = NULL;

int isBlack(Node *node) {
    return node->color == BLACK;
}
int isRed(Node *node) {
    return node->color == RED;
}
void setBlack(Node *node) {
    node->color = BLACK;
}
void setRed(Node *node) {
    node->color = RED;
}

Node* parentOf(Node *node) {
    return node->parent;
}


/*
 *         P                     P
 *        /                     /
 *       x                     y
 *      / \                   / \
 *     lx  y      ------>    x   ry
 *     / \                  / \
 *    ly ry                lx  ly
 */
void leftRotate(Node *x) {
    Node *y = x->right;
    // 处理ry节点
    x->right = y->left;
    if (y->left != NULL) {
        y->left->parent = x;
    }
    // 处理y节点
    y->parent = x->parent;
    if (x->parent == NULL) {
        // 将y设为root
        root = y;
    } else {
        // x为左节点
        if (x == x->parent->left) {
            x->parent->left = y;
        // x为右节点
        } else {
            x->parent->right = y;
        }
    }
    // 处理x节点
    x->parent = y;
    y->left = x;
}

/*
 *              p                     p
 *             /                     /
 *            y                     x
 *           / \      ------>      / \
 *          x   ry                lx  y
 *         / \                       / \
 *        lx  rx                    rx  ry
 *
 *
 */
void rightRotate(Node *y) {
    Node *x = y->left;
    // 处理rx节点
    y->left = x->right;
    if (x->right != NULL) {
        x->right->parent = y;
    }
    // 处理x节点
    x->parent = y->parent;
    if (x->parent == NULL) {
        root = x;
    } else {
        if (y == y->parent->left) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }
    }
    // 处理y节点
    y->parent = x;
    x->right = y;
}

int compare(Node *x, Node *y) {
    return x->key - y->key;
}


void insertFixUp(Node *node) {
    Node *parent, *gparent;
    while((parent = parentOf(node)) != NULL && isRed(parent)) {
        gparent = parentOf(parent);
        if (parent == gparent->left) {
            Node *uncle = gparent->right;
            if (uncle != NULL && isRed(uncle)) {
                setBlack(parent);
                setBlack(uncle);
                setRed(gparent);
                node = gparent;
                continue;
            }
            // 由于红色节点的子节点一定是黑色，因此当前节点的uncle节点一定存在
            if (node == parent->right) {
                node = parent;
                leftRotate(node);
                continue;
            } else {
                setBlack(parent);
                setRed(gparent);
                rightRotate(gparent);
            }
        } else {
            Node *uncle = gparent->left;
            if (uncle != NULL && isRed(uncle)) {
                setBlack(parent);
                setBlack(uncle);
                setRed(gparent);
                node = gparent;
                continue;
            }
            if (node == parent->left) {
                node = parent;
                rightRotate(node);
                continue;
            } else {
                setBlack(parent);
                setRed(gparent);
                leftRotate(gparent);
            }
        }
    }
    setBlack(root);
}

void insertNode(Node *node) {
    Node *current = NULL;
    Node *x = root;
    int cmp = 0;
    while (x != NULL) {
        current = x;
        cmp = compare(node, current);
        if (cmp < 0) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    node->parent = current;
    if (current != NULL) {
        if (cmp < 0) {
            current->left = node;
        } else {
            current->right = node;
        }
    } else {
        root = node;
    }
    insertFixUp(node);
}

Node* findNode(Type key) {
    Node *curent = root;
    while (curent != NULL && (key != curent->key)) {
        if (key < curent->key) {
            curent = curent->left;
        } else {
            curent = curent->right;
        }
    }
    if (curent) {
        return curent;
    }
}
int main( int argc, char **argv )
{

    for (int i = 1; i <= 100000; i++) {
        Node *node = malloc(sizeof(Node));
        memset(node, 0, sizeof(Node));
        node->key = i;
        insertNode(node);
    }

    Node *node = findNode(4000);
    printNodeInfo(node);

	return 0;
}



